package com.peng.leetcode.other;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * SolveSudoku
 *
 * @author: lupeng6
 * @create: 2020/11/18 17:31
 */
public class SolveSudoku {

    public static void main(String[] args) {
//        Set<Integer> s = new HashSet<>();
//        s.add(1);
//        s.add(2);
//        s.add(3);
//        Set<Integer> r = new HashSet<>();
//        r.add(1);
//        s.removeAll(r);
//        System.out.println(s);

//        int i = 2;
//        System.out.println(String.valueOf(i).charAt(0));

//        char[] a = new char[]{'1', '2'};
//        char[][] aa = new char[9][9];
//        aa[0] = a;
//
//        System.out.println(aa);
//
//        char[][] bb = aa.clone();
//        bb[0][0] = '9';
//
//        System.out.println(aa);

//        char[] r1 = new char[]{'5', '3', '.', '.', '7', '.', '.', '.', '.'};
//        char[] r2 = new char[]{'6', '.', '.', '1', '9', '5', '.', '.', '.'};
//        char[] r3 = new char[]{'.', '9', '8', '.', '.', '.', '.', '6', '.'};
//        char[] r4 = new char[]{'8', '.', '.', '.', '6', '.', '.', '.', '3'};
//        char[] r5 = new char[]{'4', '.', '.', '8', '.', '3', '.', '.', '1'};
//        char[] r6 = new char[]{'7', '.', '.', '.', '2', '.', '.', '.', '6'};
//        char[] r7 = new char[]{'.', '6', '.', '.', '.', '.', '2', '8', '.'};
//        char[] r8 = new char[]{'.', '.', '.', '4', '1', '9', '.', '.', '5'};
//        char[] r9 = new char[]{'.', '.', '.', '.', '8', '.', '.', '7', '9'};
//
//        [[".",".","9","7","4","8",".",".","."],["7",".",".",".",".",".",".",".","."],[".","2",".","1",".","9",".",".","."],[".",".","7",".",".",".","2","4","."],[".","6","4",".","1",".","5","9","."],[".","9","8",".",".",".","3",".","."],[".",".",".","8",".","3",".","2","."],[".",".",".",".",".",".",".",".","6"],[".",".",".","2","7","5","9",".","."]]

        char[] r1 = new char[]{'.', '.', '9', '7', '4', '8', '.', '.', '.'};
        char[] r2 = new char[]{'7', '.', '.', '.', '.', '.', '.', '.', '.'};
        char[] r3 = new char[]{'.', '2', '.', '1', '.', '9', '.', '.', '.'};
        char[] r4 = new char[]{'.', '.', '7', '.', '.', '.', '2', '4', '.'};
        char[] r5 = new char[]{'.', '6', '4', '.', '1', '.', '5', '9', '.'};
        char[] r6 = new char[]{'.', '9', '8', '.', '.', '.', '3', '.', '.'};
        char[] r7 = new char[]{'.', '.', '.', '8', '.', '3', '.', '2', '.'};
        char[] r8 = new char[]{'.', '.', '.', '.', '.', '.', '.', '.', '6'};
        char[] r9 = new char[]{'.', '.', '.', '2', '7', '5', '9', '.', '.'};


        char[][] aa = new char[9][9];
        aa[0] = r1;
        aa[1] = r2;
        aa[2] = r3;
        aa[3] = r4;
        aa[4] = r5;
        aa[5] = r6;
        aa[6] = r7;
        aa[7] = r8;
        aa[8] = r9;

        new Solution().solveSudoku(aa);
    }


    static class Solution {

        int aa = 0;
        private boolean isInit = false;
        List<List<Integer>> blankIndexes = new ArrayList<>();
        private Map<Integer, Set<Character>> rowmaps = new HashMap<>();
        private Map<Integer, Set<Character>> colmaps = new HashMap<>();
        private Map<Integer, Set<Character>> bsmap = new HashMap<>();

        public void solveSudoku(char[][] board) {
            init(board);
            solve(board, 0);
            printBoard(board);
        }

        public void printBoard(char[][] board) {
            System.out.println("\n------------------------------------");

            for (int i = 0; i < board.length; i++) {
                char[] row = board[i];
                for (char c : row) {
                    System.out.print(c + ",  ");
                }
                System.out.println();
            }
        }

        public Set<Character> getOrange() {
            Set<Character> orange = new HashSet<>();
            for (int i = 0; i < 9; i++) {
                orange.add((char)(i + 1 + 48));
            }
            return orange;
        }

        public boolean solve(char[][] board, int blankIndex) {
            //System.out.println(aa++);
            //printBoard(board);
            if (blankIndex >= this.blankIndexes.size()) {
                return true;
            }
            List<Integer> netBlank = this.blankIndexes.get(blankIndex);
            boolean flag = false;
            int x = netBlank.get(0);
            int y = netBlank.get(1);
            Set<Character> orange = getOrange();
            Set<Character> c = rowmaps.get(x);
            if (c != null) {
                orange.removeAll(c);
            }
            Set<Character> c1 = colmaps.get(y);
            if (c1 != null) {
                orange.removeAll(c1);
            }
            int bsIndex = (x / 3) * 3 + y / 3;
            Set<Character> c2 = bsmap.get(bsIndex);
            if (c2 != null) {
                orange.removeAll(c2);
            }
            if (orange.isEmpty()) {
                return false;
            }

            Iterator<Character> iterator = orange.iterator();
            while (iterator.hasNext() && !flag) {
                Character character = iterator.next();
                if (character == null) {
                    continue;
                }
                board[x][y] = character.charValue();

                c.add(character.charValue());
                c1.add(character.charValue());
                c2.add(character.charValue());
                int ne = blankIndex + 1;
                flag = solve(board, ne);

                if (!flag) {
                    c.remove(character.charValue());
                    c1.remove(character.charValue());
                    c2.remove(character.charValue());
                    board[x][y] = '.';
                } else {
                    return true;
                }
            }
            return false;
        }

        public void init(char[][] board) {
            for (int i = 0; i < board.length; i++) {
                char[] row = board[i];
                for (int j = 0; j < row.length; j++) {
                    char c = board[i][j];
                    if (c == '.') {
                        List<Integer> index = new ArrayList<>(2);
                        index.add(i);
                        index.add(j);
                        blankIndexes.add(index);
                    }

                    Set<Character> rows = rowmaps.get(i);
                    Set<Character> col = colmaps.get(j);
                    int bsIndex = (i / 3) * 3 + j / 3;
                    Set<Character> bs = bsmap.get(bsIndex);
                    if (rows == null) {
                        rows = new HashSet<>();
                        rowmaps.put(i, rows);
                    }
                    if (col == null) {
                        col = new HashSet<>();
                        colmaps.put(j, col);
                    }
                    if (bs == null) {
                        bs = new HashSet<>();
                        bsmap.put(bsIndex, bs);
                    }
                    if (c != '.') {
                        rows.add(c);
                        col.add(c);
                        bs.add(c);
                    }
                }
            }
        }
    }
}
